package org.example.linkedList;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Auther: wangbw @Date:2020/12/17 @Description: org.example.linkedList @version: 1.0
 */
public class BucketSort {
    public static void main(String[] args) {
        int[] arr = new int[]{21, 8, 6};
        sort(arr);
        print(arr);
    }

    private static void sort(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        int bucketSize = arr.length / 10 + 1;
        int min = arr[0], max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < min) min = arr[i];
            if (arr[i] > max) max = arr[i];
        }
        List<ArrayList<Integer>> bucktes = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < bucketSize; i++) bucktes.add(new ArrayList<Integer>());
        int span = (max - min + 1) / bucketSize;
        for (int i = 0; i < arr.length; i++) {
            int index = (arr[i] - min) / span;
            bucktes.get(index).add(arr[i]);
        }
        int index = 0;
        for (int i = 0; i < bucketSize; i++) {
            List<Integer> list = bucktes.get(i);
            sort(list);
            for (int j = 0; j < list.size(); j++) arr[index++] = list.get(j);
        }
    }

    private static void sort(List<Integer> list) {
        if (list == null || list.size() <= 1)
            return;
        for (int i = 1; i < list.size(); i++) {
            int temp = list.get(i);
            int j = i - 1;
            for (; j >= 0 && list.get(j) > temp; j--)
                list.set(j + 1, list.get(j));
            list.set(j + 1, temp);
        }
    }

    private static void print(int[] arr) {
        System.out.println("result:" + Arrays.toString(arr));
    }
}
